#include<stdio.h>
#include<iostream>
//#include<ciostream.h>

#include<string.h>
using namespace std;

const int num_chars=26;

char* a,b;

class Trie
{
public:
    Trie();
    Trie(Trie& tr);
    virtual ~Trie();

    int trie_search(const char* word,char* entry) const;
    int insert(const char* word,const char* entry);
    int remove(const char* word,const char* entry);

protected:
    struct Trie_node
    {
        char* data;
        Trie_node* branch[num_chars];
        Trie_node();
    };

    Trie_node* root;
};

Trie::Trie_node::Trie_node()
{
    data=NULL;
    for(int i=0;i<num_chars;i++)
    {
        branch[i]=NULL;
    }
}

Trie::Trie():root(NULL){}

Trie::~Trie(){}

int Trie::trie_search(const char* word,char* entry) const
{
    int position=0;
    char char_code;
    Trie_node *location=root;

    while(location!=NULL && *word!=0)
    {
        if(*word>='A' && *word<='Z')
            char_code=*word-'A';
        if(*word>='a' && *word<='z')
            char_code=*word-'a';
        else return 0;

        location=location->branch[char_code];
        position++;
        word++;
    }
    if(location!=NULL && location->data!=NULL)
    {
        strcpy(entry,location->data);
        return position;
    }
    else return 0;
}

int Trie::insert(const char* word,const char* entry)
{
    int position=0;
    if(root==NULL) root=new Trie_node();

    char char_code;
    Trie_node *location=root;

    while(location!=NULL && *word!=0)
    {
        if(*word>='A' && *word<='Z')
            char_code=*word-'A';
        if(*word>='a' && *word<='z')
            char_code=*word-'a';
        else return 0;

        /**
            This line is to add new physical node to
                the whole trie tree.____important.
        */
        if(location->branch[char_code]==NULL)
            location->branch[char_code]=new Trie_node();

        location=location->branch[char_code];
        position++;
        word++;
    }
    if(location->data!=NULL) return 0;
    else
    {
        //printf("%s\n",word);
        //printf("%s\n",entry);
        //int i=strlen(entry)+1;
        //location->data=new char[strlen(entry)+1];
        //strcpy(location->data,entry);
        return 1;
    }
    //*/
}

int main()
{
    Trie t;
    char entry[100];
    t.insert("aa","DET");
    t.insert("abacus","NOUN");
  	t.insert("abalone","NOUN");
  	t.insert("abandon","VERB");
  	t.insert("abandoned","ADJ");
  	t.insert("abashed","ADJ");
  	t.insert("abate","VERB");
  	t.insert("this", "PRON");

  	 if (t.trie_search("this", entry))
        cout<<"'this' was found. pos: "<<entry<<endl;
    if (t.trie_search("abate", entry))
        cout<<"'abate' is found. pos: "<<entry<<endl;
    if (t.trie_search("baby", entry))
        cout<<"'baby' is found. pos: "<<entry<<endl;
    else
        cout<<"'baby' does not exist at all!"<<endl;

    if (t.trie_search("aa", entry))
        cout<<"'aa was found. pos: "<<entry<<endl;
    //*/
}
